package java学习.算法.二叉树;

import java.util.ArrayList;
import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/5 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 二叉树中和为某一值的路径 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    public boolean hasPathSum (TreeNode root, int sum) {
        // 备好两个栈： 记录当前节点
        Stack<TreeNode> stack = new Stack<>();
        // 记录当前的总和
        Stack<Integer> stack1 = new Stack<>();
        stack.push(root);
        stack1.push(root.val);

        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            stack1.pop();
            if (pop.left==null&&pop.left==null&&pop.val==sum){
                return  true;
            }
            if (pop.left!=null){
                stack.push(pop.left);
                stack1.push(pop.val+pop.left.val);
            }
            if (pop.right!=null){
                stack.push(pop.right);
                stack1.push(pop.val+pop.right.val);
            }
        }
        return false;

    }
    public boolean hasPathSum1 (TreeNode root, int sum) {
        boolean left = false;boolean right = false;


        if (root==null){
            return false;
        }

        if (root.left == null && root.right == null && sum == root.val )
            return true;


        left = hasPathSum(root.left, sum-root.val);

        right = hasPathSum(root.right, sum-root.val );

        return left||right;
    }
    /**
     * 二叉树中和为某一值的路径2
     * @param root
     * @param expectNumber
     * @return
     */
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {

         dfs( root,  expectNumber,new ArrayList<Integer>());
        return list;

    }

    public void dfs(TreeNode root, int expectNumber, ArrayList<Integer> treeNodes) {
        if (root==null){
            return ;
        }
        treeNodes.add(root.val);
        expectNumber-=root.val;
        if (root.left==null&&root.right==null&&expectNumber==0){
            list.add(treeNodes);
        }
        dfs(root.left,expectNumber,treeNodes);
        dfs(root.right,expectNumber,treeNodes);

        treeNodes.remove(treeNodes.size()-1);  // 删除最后一个节点

    }

    public void dfsadd(TreeNode root,int sum,int expectNumber, ArrayList<Integer> treeNodes) {
        if (root==null){
            return ;
        }
        treeNodes.add(root.val);
        sum+=root.val;
        if (root.left==null&&root.right==null&&expectNumber==sum){
            list.add(treeNodes);
        }
        dfsadd(root.left,sum,expectNumber,treeNodes);
        dfsadd(root.right,sum,expectNumber,treeNodes);

        treeNodes.remove(treeNodes.size()-1);  // 删除最后一个节点

    }

}
